class Solution {
public:
    int numWays(int n) {
        int result[2] = {1,1};
        if(n < 0){
            return -1;
        }else if(n < 2){
            return result[n];
        }else{
            //n >= 2
            //最后一步有两种情况：上一步在n-1级或上一步在n-2级台阶，所以numWays(n) = numWays(n-1) + numWays(n-2)
            //把大问题分解成若干小问题，该问题存在大量重复的+1、+2，先求小问题的最优解
            //本题是斐波那契数列的拓展，即f(n) = f(n - 1) + f(n - 2)
            int allSteps = 2;  //记录当前的台阶数
            int ways = 1;  //numWays(1),往后是numWays(n)
            int waysMinusOne = 1;  //numWays(1),往后是numWays(n - 1)
            int waysMinusTwo = 1;  //numWays(0),,往后是numWays(n - 2)

            while(allSteps <= n){
                ways = (waysMinusOne + waysMinusTwo) % 1000000007;
                waysMinusTwo = waysMinusOne % 1000000007;
                waysMinusOne = ways;
                allSteps++;
            }

            return ways;
        }
    }
};